#include<iostream>
#include<queue>
#include<stack>
#include<vector>

using namespace std;

struct BinaryTreeNode{
    int value;
    BinaryTreeNode * left;
    BinaryTreeNode * right;
};

BinaryTreeNode * createNode (int value){
    BinaryTreeNode * node = new BinaryTreeNode();
    node -> value = value;
    node -> left = node -> right = nullptr;
    return node;
}

void connectNode ( BinaryTreeNode * root, BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
    root -> right = right;
}

// 32_02 路径问题： 

void findPath(BinaryTreeNode * root , int pathSum, int currentSum, vector<int> &path){

    currentSum += root->value;
    path.push_back(root->value);

    bool isLeaf = root -> left == nullptr && root -> right == nullptr ;
    if ( currentSum == pathSum && isLeaf ){
        // 找到一条路径
        for ( int i = 0; i < path.size(); i++ ){
            cout << path[i] << "  ";
        }
        cout << endl;
    }
        if ( root -> left != nullptr){
            findPath(root->left, pathSum, currentSum, path);
        }
        if ( root -> right != nullptr){
            findPath(root->right, pathSum, currentSum, path);
        }
   path.pop_back();
}

void pathInTree( BinaryTreeNode * root, int pathSum ){
	if ( root == nullptr )
		return;
    int currentSum = 0;
	vector<int> vect;
    findPath(root, pathSum, currentSum, vect);
} 

int main(void){
    BinaryTreeNode * node1 = createNode(2);
    BinaryTreeNode * node2 = createNode(3);
    BinaryTreeNode * node3 = createNode(4);
    BinaryTreeNode * node4 = createNode(5);
    BinaryTreeNode * node5 = createNode(8);
    BinaryTreeNode * node6 = createNode(7);
    BinaryTreeNode * node7 = createNode(8);
    BinaryTreeNode * node8 = createNode(9);
    BinaryTreeNode * node9 = createNode(10);
    BinaryTreeNode * node10 = createNode(11);
    BinaryTreeNode * node11 = createNode(12);

    connectNode(node1,node2,node3);
    connectNode(node2,node4,node5);
    connectNode(node3,node6,node7);
    connectNode(node4,node8,nullptr);
    connectNode(node7,node9,node10);

    // Test 1
    pathInTree(node1, 13);
    return 0;
}